10109. Tree Minimum depth

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Definition of a tree:

//Java

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

left = null;

right = null;

}

}

// C++

class TreeNode

{

public:

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

Implement function minDepth that returns the minimum depth of the tree.

// Java

int minDepth (TreeNode tree)

// C++

int minDepth(TreeNode *tree)

Example

Function minDepth returns 2 because the shortest path from the root 5 to the nearest leaf 10 contains 2 nodes.

SOLUTION

binary tree

Algorithm analysis

If tree = NULL, the minimum depth of the tree is 0.

If the tree does not have a left son, then the minimum depth of the tree equals to the minimum depth of the right subtree plus 1.

If the tree does not have a right son, then the minimum depth of the tree equals to the minimum depth of the left subtree plus 1.

Otherwise find the minimum depth of the left h₁ and right h₂ subtree and return the value of min(h₁, h₂) + 1.

Algorithm realization

int minDepth(TreeNode* tree)

{

If tree = NULL, the minimum depth of the tree is 0.

if (tree == NULL) return 0;

If the tree does not have a left son, then the minimum depth of the tree equals to the minimum depth of the right subtree plus 1.

if (tree->left == NULL)

return minDepth(tree->right) + 1;

If the tree does not have a right son, then the minimum depth of the tree equals to the minimum depth of the left subtree plus 1.

if (tree->right == NULL)

return minDepth(tree->left) + 1;

Find the minimum depth of the left h₁ and right h₂ subtree. Return the value of min(h₁, h₂) + 1.

int Left = minDepth(tree->left);

int Right = minDepth(tree->right);

return min(Left, Right) + 1;

}

Java realization

int minDepth(TreeNode tree)

{

if (tree == null) return 0;

if (tree.left == null)

return minDepth(tree.right) + 1;

if (tree.right == null)

return minDepth(tree.left) + 1;

int Left = minDepth(tree.left);

int Right = minDepth(tree.right);

return Math.min(Left, Right) + 1;

}